package leetcode

import kotlinetc.println

//https://leetcode.com/problems/unique-paths-iii/
/**
On a 2-dimensional grid, there are 4 types of squares:

1 represents the starting square.  There is exactly one starting square.
2 represents the ending square.  There is exactly one ending square.
0 represents empty squares we can walk over.
-1 represents obstacles that we cannot walk over.
Return the number of 4-directional walks from the starting square to the ending square, that walk over every non-obstacle square exactly once.



Example 1:

Input: [[1,0,0,0],[0,0,0,0],[0,0,2,-1]]
Output: 2
Explanation: We have the following two paths:
1. (0,0),(0,1),(0,2),(0,3),(1,3),(1,2),(1,1),(1,0),(2,0),(2,1),(2,2)
2. (0,0),(1,0),(2,0),(2,1),(1,1),(0,1),(0,2),(0,3),(1,3),(1,2),(2,2)
Example 2:

Input: [[1,0,0,0],[0,0,0,0],[0,0,0,2]]
Output: 4
Explanation: We have the following four paths:
1. (0,0),(0,1),(0,2),(0,3),(1,3),(1,2),(1,1),(1,0),(2,0),(2,1),(2,2),(2,3)
2. (0,0),(0,1),(1,1),(1,0),(2,0),(2,1),(2,2),(1,2),(0,2),(0,3),(1,3),(2,3)
3. (0,0),(1,0),(2,0),(2,1),(2,2),(1,2),(1,1),(0,1),(0,2),(0,3),(1,3),(2,3)
4. (0,0),(1,0),(2,0),(2,1),(1,1),(0,1),(0,2),(0,3),(1,3),(1,2),(2,2),(2,3)
Example 3:

Input: [[0,1],[2,0]]
Output: 0
Explanation:
There is no path that walks over every empty square exactly once.
Note that the starting and ending square can be anywhere in the grid.


Note:

1 <= grid.length * grid[0].length <= 20
Accepted
9,084
Submissions
12,802
 */
fun main(args: Array<String>) {


    //[1,0,0,0],[0,0,0,0],[0,0,2,-1]

    //[[0,0,0,1,-1,-1,0,-1,2,0]]
    val grid = arrayOf(
            intArrayOf(1, 0, 0, 0),
            intArrayOf(0, 0, 0, 0),
            intArrayOf(0, 0, 2, -1)
    )

    val grid1 = arrayOf(intArrayOf(0,0,0,1,-1,-1,0,-1,2,0))
    uniquePathsIII(grid).println()
}


//深度优先遍历，递归
fun uniquePathsIII(grid: Array<IntArray>): Int {

    //先计算0有多少个，也就是总步数
    val m = grid.size //行
    val n = grid[0].size  //列

    var startX = 0
    var startY = 0

    //记录哪些位置是走过的
    val visited = Array(m) { Array(n) { false } }

    var stepMax = 1  //除了每个0 需要走一步，走到终点还需要一步，所以初始化为1
    for (i in 0 until m) {
        for (j in 0 until n) {
            if (grid[i][j] == 0) stepMax++

            if (grid[i][j] == 1) {
                startX = j
                startY = i
            }
        }
    }

    //找到起始位置

    visited[startY][startX] = true

    return uniquePathsIIIRecursive(grid, visited, startX, startY, 0, stepMax)
}

fun uniquePathsIIIRecursive(grid: Array<IntArray>, visited: Array<Array<Boolean>>, startX: Int, startY: Int, step: Int, stepMax: Int): Int {
    if (step == stepMax && grid[startY][startX] == 2) return 1

    //有四个方向可以走,有能走的方向就继续走了，不然就返回0

    var left = 0
    var right = 0
    var top = 0
    var bottom = 0


    //以下判断太长,判断反向

    //left
    if (startX - 1 >= 0 && visited[startY][startX - 1].not() && grid[startY][startX - 1] != -1) {
        visited[startY][startX - 1] = true
        left = uniquePathsIIIRecursive(grid, visited, startX - 1, startY, step + 1, stepMax)
        visited[startY][startX - 1] = false
    }

    if (startX + 1 < grid[0].size && visited[startY][startX + 1].not() && grid[startY][startX + 1] != -1) {
        visited[startY][startX + 1] = true
        right = uniquePathsIIIRecursive(grid, visited, startX + 1, startY, step + 1, stepMax)
        visited[startY][startX + 1] = false
    }

    if (startY - 1 >= 0 && visited[startY - 1][startX].not() && grid[startY - 1][startX] != -1) {
        visited[startY - 1][startX] = true
        top = uniquePathsIIIRecursive(grid, visited, startX, startY - 1, step + 1, stepMax)
        visited[startY - 1][startX] = false
    }

    if (startY + 1 < grid.size && visited[startY + 1][startX].not() && grid[startY + 1][startX] != -1) {
        visited[startY + 1][startX] = true
        bottom = uniquePathsIIIRecursive(grid, visited, startX , startY+1, step + 1, stepMax)
        visited[startY + 1][startX] = false
    }

    return left + right + top + bottom
}
